package Algorithm.Sort;

import java.util.Arrays;

public class QuickSortThree {
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 三路快排
     *
     * @param
     */
    public static void quickSort3(int[] arr) {
        quickSortInternal3(arr, 0, arr.length - 1);
    }

    private static void quickSortInternal3(int[] arr, int l, int r) {
        if (l > r) {
            return;
        }
//        int randomIndex = random.nextInt(l,r);
//        swap(arr,l,randomIndex);
        int v = arr[l];
        // 这些变量的取值，一定是满足区间的定义，最开始的时候，所有区间都是空
        // arr[l + 1..lt] < v
        // lt是指向最后一个<v的元素
        int lt = l;
        // arr[lt + 1..i) == v
        // i - 1是最后一个 = v的元素
        int i = lt + 1;
        // arr[gt..r] > v
        // gt是第一个 > v的元素
        int gt = r + 1;
        // i从前向后扫描和gt重合时，所有元素就处理完毕
        while (i < gt) {
            if (arr[i] < v) {
                // arr[l + 1..lt] < v
                // arr[lt + 1..i) == v
                swap(arr, i, lt + 1);
                i++;
                lt++;
            } else if (arr[i] > v) {
                // 交换到gt - 1
                swap(arr, i, gt - 1);
                gt--;
                // 此处i不++，交换来的gt - 1还没有处理
            } else {
                // 此时arr[i] = v
                i++;
            }
        }
        // lt落在最后一个 < v的索引处
        swap(arr, l, lt);
        // arr[l..lt - 1] < v
        quickSortInternal3(arr, l, lt - 1);
        // arr[gt..r] > v
        quickSortInternal3(arr, gt, r);
    }

    public static void main(String[] args) {
        int[] arr2 = {9, 1, 5, 8, 3, 7, 4, 6, 2};
        quickSort3(arr2);
        System.out.println(Arrays.toString(arr2));

    }
}
